package cn.kent.middle;

/**
 * 641. 设计循环双端队列
 */
public class MyCircularDeque {
    public static void main(String[] args) {
        MyCircularDeque deque = new MyCircularDeque(4);
        System.out.println(deque.isEmpty());
        deque.insertFront(1);
        deque.insertFront(2);
        deque.insertLast(3);
        System.out.println(deque.getFront());
        System.out.println(deque.getRear());
        System.out.println(deque.isFull());
        deque.insertLast(4);
        System.out.println(deque.insertLast(5));
        System.out.println(deque.isFull());
        deque.deleteFront();
        deque.deleteLast();
        System.out.println(deque.getFront());
        System.out.println(deque.getRear());
    }

    // 队列
    private int[] q;
    private int headIndex; // 头结点索引
    private int count; // 队列长度
    private int capacity; // 队列容量

    //构造函数,双端队列最大为 k
    public MyCircularDeque(int k) {
        this.q = new int[k];
        this.headIndex = 0;
        this.count = 0;
        this.capacity = k;
    }

    // 将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
    public boolean insertFront(int value) {
        // 判断队满，返回false
        if (isFull())
            return false;
        headIndex = (headIndex + capacity - 1) % capacity;
        q[headIndex] = value;
        count++;
        return true;
    }

    // 将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
    public boolean insertLast(int value) {
        // 判断队满，返回false
        if (isFull())
            return false;
        int tailIndex = (headIndex + count) % capacity;
        q[tailIndex] = value;
        this.count++;
        return true;
    }

    // 从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
    public boolean deleteFront() {
        // 判断队空，返回false
        if (isEmpty())
            return false;
        headIndex = (headIndex + capacity + 1) % capacity;
        count--;
        return true;
    }

    // 从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
    public boolean deleteLast() {
        // 判断队空，返回false
        if (isEmpty())
            return false;
        count--;
        return true;
    }

    // 从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
    public int getFront() {
        if (isEmpty())
            return -1;
        return q[headIndex];
    }

    // 获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
    public int getRear() {
        if (isEmpty())
            return -1;
        return q[(headIndex + count - 1) % capacity];
    }

    // 若双端队列为空，则返回 true ，否则返回 false  。
    public boolean isEmpty() {
        return count == 0;
    }

    // 若双端队列满了，则返回 true ，否则返回 false 。
    public boolean isFull() {
        return count == capacity;
    }
}
